#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back

typedef double db;

const db EPS = 1e-8;
const db INF = 1e100;

inline int sgn(db x, db E = EPS){return x<-E?-1:x>E;}

inline int cmp(db a,db b,db E = EPS){return sgn(a-b, E);}

struct P{
	db x,y;
	P operator+(P o){return {x+o.x,y+o.y};}
	P operator-(P o){return {x-o.x,y-o.y};}
	P operator-(){ return {-x,-y}; }
	db det(P o){return x*o.y-y*o.x;}
	db dot(P o){return x*o.x+y*o.y;}
    P operator*(db d) { return {x * d, y * d}; }
    P operator/(db d) { return {x / d, y / d}; }

	bool operator<(P o) const { return cmp(x,o.x) != 0? cmp(x,o.x) == -1 : cmp(y,o.y) == -1; }
	bool operator>(P o) const { return cmp(x,o.x) != 0? cmp(x,o.x) == 1 : cmp(y,o.y) == 1; }

	bool operator==(P o){ return cmp(x,o.x) == 0 && cmp(y,o.y) == 0; }

	void read(){
		scanf("%lf%lf",&x,&y);
	}
    db abs() { return sqrt(abs2());}
    db abs2() { return x * x + y * y; }
    P rot90() { return {-y,x};}
    P unit() { return *this/abs(); }
}O = (P){0,0};

#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))
#define crossOp(p1,p2,p3) sgn(cross(p1,p2,p3))

P isLL(P p1, P p2, P q1, P q2) {
    db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
    return (p1 * a2 + p2 * a1) / (a1 + a2);
}

vector<P> convexHull(vector<P> ps) {
    int n = ps.size(); if(n <= 1) return ps;
    sort(ps.begin(), ps.end());
    vector<P> qs(n * 2); int k = 0;
    for (int i = 0; i < n; qs[k++] = ps[i++])
        while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
    for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
        while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
    qs.resize(k - 1);
    return qs;
}

struct CH{
	int n;

	vector<P> ps, lower, upper;

	P operator[](int i){return ps[i];}

	int find(vector<P>&vec, P dir){ // 距dir方向最近的凸包上的点
		int l=0,r=vec.size();
		while(l+5<r){
			int L = (l*2+r)/3, R = (l+r*2)/3;
			if(vec[L].dot(dir) > vec[R].dot(dir))
				r=R;
			else
				l=L;
		}
		int ret = l; rep(k,l+1,r) if(vec[k].dot(dir) > vec[ret].dot(dir)) ret = k;
		return ret;
	}

	/*
	ps[0] must be the smallest one!
	*/

	void init(vector<P> _ps){
		ps = _ps; n = ps.size();

		rotate(ps.begin(),min_element(ps.begin(), ps.end()),ps.end());

		int at = max_element(ps.begin(), ps.end()) - ps.begin();

		lower = vector<P>(ps.begin(),ps.begin() + at + 1);

		upper = vector<P>(ps.begin()+at,ps.end()); upper.pb(ps[0]);
	}

	int findFarest(P dir){
		if(dir.y > 0 || dir.y==0 && dir.x > 0){
			return ( (int)lower.size() -1 + find(upper,dir)) % n;
		} else {
			return find(lower,dir);
		}
	}

	P get(int l,int r,P p1,P p2){ // 编号[l,r]区间内直线与凸包的交点
		int sl = crossOp(p1,p2,ps[l%n]);
		while(l+1<r){
			int m = (l+r)>>1;
			if(crossOp(p1,p2,ps[m%n]) == sl)
				l = m;
			else
				r = m;
		}
		return isLL(p1,p2,ps[l%n],ps[(l+1)%n]);
	}

	vector<P> getIS(P p1,P p2){ // 凸包与直线交点，严格
		int X = findFarest((p2-p1).rot90());
		int Y = findFarest((p1-p2).rot90());
		if(X > Y) swap(X,Y);
		if(crossOp(p1,p2,ps[X]) * crossOp(p1,p2,ps[Y]) < 0){
			return {get(X,Y,p1,p2),get(Y,X+n,p1,p2)};
		} else {
			return {};
		}
	}

	void update_tangent(P p, int id, int&a,int&b){
		if(crossOp(p,ps[a],ps[id]) > 0) a = id;
		if(crossOp(p,ps[b],ps[id]) < 0) b = id;
	}

	void binary_search(int l,int r,P p,int&a,int&b){
		if(l==r) return;
		update_tangent(p,l%n,a,b);
		int sl = crossOp(p,ps[l%n],ps[(l+1)%n]);
		while(l+1<r){
			int m = l+r>>1;
			if(crossOp(p,ps[m%n],ps[(m+1)%n]) == sl)
				l=m;
			else
				r=m;
		}
		update_tangent(p,r%n,a,b);
	}

	bool contain(P p){ // 点在凸包内
		if(p.x < lower[0].x || p.x > lower.back().x) return 0;
		int id = lower_bound(lower.begin(), lower.end(),(P){p.x,-INF}) - lower.begin();
		if(lower[id].x == p.x){
			if(lower[id].y > p.y) return 0;
		} else {
			if(crossOp(lower[id-1],lower[id],p) < 0) return 0;
		}
		id = lower_bound(upper.begin(), upper.end(),(P){p.x,INF},greater<P>()) - upper.begin();
		if(upper[id].x == p.x){
			if(upper[id].y < p.y) return 0;
		} else {
			if(crossOp(upper[id-1],upper[id],p) < 0) return 0;
		}
		return 1;
	}

	bool get_tangent(P p,int&a,int&b){ // 求切线 b->a
		if(contain(p)) return 0;
		a=b=0;
		int id = lower_bound(lower.begin(), lower.end(),p) - lower.begin();
		binary_search(0,id,p,a,b);
		binary_search(id,lower.size(),p,a,b);
		id = lower_bound(upper.begin(), upper.end(),p,greater<P>()) - upper.begin();
		binary_search((int)lower.size() - 1, (int) lower.size() - 1 + id,p,a,b);
		binary_search((int) lower.size() - 1 + id,(int) lower.size() - 1 + upper.size(),p,a,b);
		return 1;
	}
};

int main() {
    return 0;
}
